package com.fanshuai.search;

public class SearchUtil {
    /**
     * 二分搜索  用于有序数组搜索
     * @param a
     * @param value
     * @return
     */
    public static int binarySearch(int[] a, int value) {
        int start = 0;
        int end = a.length - 1;
        int mid = (start + end) / 2;

        while (start <= end) {
            if (a[mid] == value) {
                return mid;
            }
            if (a[mid] > value) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return -1;
    }

    /**
     * 二分查找  递归实现
     * @param a
     * @param value
     * @return
     */
    public static int binarySearch2(int[] a, int value, int start, int end) {
        if (start > end) {
            return -1;
        }

        int mid = (start + end) / 2;
        if (value == a[mid]) {
            return mid;
        } else if (value < a[mid]) {
            return binarySearch2(a, value, start, mid - 1);
        } else {
            return binarySearch2(a, value, mid + 1, end);
        }
    }
}
